package 中等.并查集;

/**
 * 给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。
 * 其中  s1[i] 和 s2[i]  是一组等价字符。
 * 举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。
 * 等价字符遵循任何等价关系的一般规则：
 * 自反性 ：'a' == 'a'
 * 对称性 ：'a' == 'b' 则必定有 'b' == 'a'
 * 传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'
 * 例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，
 * 而 "aab" 是 baseStr 的按字典序最小的等价字符串
 * 利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。
 *
 * @ https://leetcode.cn/problems/lexicographically-smallest-equivalent-string/description/?envType=daily-question&envId=2025-06-05
 * @date 2025/06/05
 */
public class 按字典序排列最小的等效字符串_1061 {

    public static void main(String[] args) {
        DSU dsu = new DSU(26);

        String s1 = "leetcode", s2 = "programs";
        for (int i = 0; i < s1.length(); i++) {
            dsu.union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }

        System.out.println(dsu.connected('s' - 'a', 'a' - 'a'));

    }

    /**
     * 并查集
     */
    public String smallestEquivalentString(String s1, String s2, String baseStr) {

        DSU dsu = new DSU(26);
        for (int i = 0; i < s1.length(); i++) {
            dsu.union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }

        StringBuilder stringBuilder = new StringBuilder();

        for (char c : baseStr.toCharArray()) {
            char cur = c;
            for (int i = 0; i < 26; i++) {
                if (dsu.connected(c - 'a', i)) {
                    cur = (char) ('a' + i);
                    break;
                }
            }
            stringBuilder.append(cur);
        }

        return stringBuilder.toString();
    }

    static class DSU {

        private int[] pre;

        public DSU(int n) {
            this.pre = new int[n];
            for (int i = 0; i < n; i++) {
                pre[i] = i;
            }
        }

        private int findAndUpdate(int x) {
            if (pre[x] == x) {
                return x;
            }
            return pre[x] = findAndUpdate(pre[x]);
        }

        private void union(int x, int y) {
            int preX = findAndUpdate(x);
            pre[preX] = findAndUpdate(y);
        }

        private boolean connected(int x, int y) {
            return findAndUpdate(x) == findAndUpdate(y);
        }

    }

}
